import java.util.Iterator;
import java.util.List;
import java.util.ArrayList;
import java.util.Random;

public class RandomIterator<E> implements Iterator<E> {

	private final boolean[] served;
	private int servedcount = 0;
	private final List<E> list;
	private final int LIST_SIZE;
	private final Random rand;
	private int lower,upper;
	private int index,range;

	public RandomIterator (ArrayList<E> list , Random rand){
		this.list=list;
		this.rand = rand;
		LIST_SIZE = list.size();
		served = new boolean[LIST_SIZE];
		lower=0;
		upper = LIST_SIZE-1;
	}

	public boolean hasNext() {
		return (servedcount<LIST_SIZE);
	}

	public E next() {
		range = upper-lower+1;
		do{
			index=lower+rand.nextInt(range);
		}while(served[index]);
		if (index==lower)
			lower++;
		else if (index==upper)
			upper--;
		served[index]=true;
		servedcount++;
		return (list.get(index));
		
	}

	@Override
	public void remove() {
		throw (new UnsupportedOperationException());

	}

 

}
